#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "treecommon.h"

// 通过广义表实现二叉树的创建
BinTree createByGeneralize(char *str)
{
    // str 为存储广义表的字符串指针
    // 用指针数组模拟栈
    BinNode *BN[100];
    int top = -1; // 置空栈

    BinNode *cur = NULL;
    BinTree BT = NULL;

    int k, j = 0;
    char ch = str[j];

    // 循环遍历广义表字符
    while (ch != '\0')
    {
        // printf("----->%c", ch);
        switch (ch)
        {
        case '(': // 字符为左括号则进栈
            top++;
            BN[top] = cur;
            k = 1; // 左括号前的字符为左结点
            break;
        case ')': // 字符为右括号则出栈
            top--;
            break;
        case ',':
            k = 2; // 逗号后的字符为右结点(不包含括号字符)
            break;
        default:
            cur = (BinTree)malloc(sizeof(BinNode));
            cur->data = ch;
            cur->lchild = cur->rchild = NULL;

            // BT为null 则说明是根结点
            if (BT == NULL)
                BT = cur;
            else
            {
                // k=1 是左节点，k=2为右结点
                if (k == 1)
                    BN[top]->lchild = cur;
                else if (k == 2)
                    BN[top]->rchild = cur;
            }
            break;
        }

        j++;
        ch = str[j];
    }

    return BT;
}

// 通过完全二叉树层次输入结点信息创建
BinTree createByCompleteTree()
{
    // 是一个BinNode类型的指针数组，front 和 rear 分别是队头和队尾指针
    BinNode *Q[100];

    BinNode *cur;
    BinTree BT = NULL;

    int front = 1, rear = 0;

    printf(">>input char element: ");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        cur = NULL;
        if (ch != '@')
        {
            // 新结点申请、赋值
            cur = (BinTree)malloc(sizeof(BinNode));
            cur->data = ch;
            cur->lchild = cur->rchild = NULL;
        }
        rear++;
        Q[rear] = cur;
        // 为1则说明是根结点
        if (rear == 1)
            BT = cur;
        else
        {
            // 结点不为null 且出队不为null
            if (cur != NULL && Q[front] != NULL)
            {
                // 偶数则新结点为左孩子， 奇数为右孩子
                if (rear % 2 == 0)
                    Q[front]->lchild = cur;
                else
                    Q[front]->rchild = cur;
            }

            // 为奇数，front 指向下一个双亲
            if (rear % 2 != 0)
                front++;
        }
    }

    return BT;
}

// ------------------------------递归遍历--------------------------
/**
 * 中序遍历:
 */
void inorder(BinTree tree)
{
    if (tree == NULL)
    {
        // printf("[inorder] the tree is empty\n");
        return;
    }
    inorder(tree->lchild);
    printf("%c ", tree->data);
    inorder(tree->rchild);
}

/**
 * 前序遍历:
 */
void preorder(BinTree tree)
{
    if (tree == NULL)
    {
        // printf("[inorder] the tree is empty\n");
        return;
    }
    printf("%c ", tree->data);
    preorder(tree->lchild);
    preorder(tree->rchild);
}

/**
 * 后序遍历:
 */
void postorder(BinTree tree)
{
    if (tree == NULL)
    {
        // printf("[inorder] the tree is empty\n");
        return;
    }
    postorder(tree->lchild);
    postorder(tree->rchild);
    printf("%c ", tree->data);
}

// -----------------------------非递归遍历------------------------------
/**
 * 中序遍历: 利用栈的非递归遍历
 */
void s_inorder(BinTree tree)
{
    LinkStack LS = NULL;
    BinTree p;

    push(&LS, tree);
    while (!stackEmpty(LS))
    {
        // 直至左子树空为止
        while (getTop(LS))
        {
            push(&LS, getTop(LS)->lchild);
        }
        // 空指针退栈
        p = pop(&LS);
        if (!stackEmpty(LS))
        {
            printf("%c ", getTop(LS)->data);
            p = pop(&LS);
            push(&LS, p->rchild); // 右子树进栈
        }
    }
}
// 栈的中序遍历，一个循环
void s2_inorder(BinTree tree)
{
    BinTree current = tree;

    LinkStack LS = NULL;
    int done = 0;

    while (!done)
    {
        if (current != NULL)
        {
            push(&LS, current);
            current = current->lchild;
        }
        else
        {
            if (!stackEmpty(LS))
            {
                current = pop(&LS);
                printf("%d ", current->data);
                current = current->rchild;
            }
            else
            {
                done = 1;
            }
        }
    }
}

/**
 * 前序遍历: 利用栈的非递归遍历.
 */
void s_preorder(BinTree tree)
{
    LinkStack LS = NULL;
    push(&LS, tree);
    while (!stackEmpty(LS))
    {
        tree = pop(&LS);
        if (tree != NULL)
        {
            printf("%c ", tree->data);
            push(&LS, tree->rchild);
            push(&LS, tree->lchild);
        }
    }
}

/**
 * 中序遍历: 利用指针数组实现
 */
void p_inorder(BinTree tree)
{
    BinNode *SN[100];

    int top = 0;
    SN[top] = tree;

    do
    {
        // 遍历左节点
        while (SN[top] != NULL)
        {
            top = top + 1;
            SN[top] = SN[top - 1]->lchild;
        }

        // 求出最底层的左结点的下标，并打印。然后看是否有右结点，没有则找它双亲结点
        top = top - 1;
        if (top >= 0)
        {
            printf("%c ", SN[top]->data);
            SN[top] = SN[top]->rchild;
        }
    } while (top != -1);
}

/**
 * 非递归: 按层遍历二叉树链表。按层次从左往右输出
 */
void transLevel(BinTree tree)
{
    if (tree == NULL)
    {
        return;
    }

    LNode n;
    LinkQueue Q = &n; // 防止Q未定义，导致奇怪问题
    initQueue(Q);

    printf("%c ", tree->data);
    enQueue(Q, tree);
    while (!queueEmpty(Q))
    {
        tree = deQueue(Q);
        if (tree->lchild != NULL)
        {
            printf("%c ", tree->lchild->data);
            enQueue(Q, tree->lchild);
        }

        if (tree->rchild != NULL)
        {
            printf("%c ", tree->rchild->data);
            enQueue(Q, tree->rchild);
        }
    }
}

// 莫里斯前序遍历
void morrisPreorder(BinTree tree)
{
    while (tree)
    {
        // 如果树的左结点为空，则打印当前结点的数据，然后移到右边的结点
        if (tree->lchild == NULL)
        {
            printf("%c ", tree->data);
            tree = tree->rchild;
        }
        else
        {
            //
            BinNode *current = tree->lchild;
            while (current->rchild && current->rchild != tree)
            {
                current = current->rchild;
            }
            if (current->rchild == tree)
            {
                current->rchild = NULL;
                tree = tree->rchild;
            }
            else
            {
                printf("%c ", tree->data);
                current->rchild = tree;
                tree = tree->lchild;
            }
        }
    }
}

// -----------------------------深度、查找等--------------------------
/**
 * 求二叉树树的深度
 */
int treeMaxDepth(BinTree tree)
{
    if (tree == NULL)
    {
        return 0;
    }
    int leftDepth = treeMaxDepth(tree->lchild);
    int rightDepth = treeMaxDepth(tree->rchild);

    if (leftDepth > rightDepth)
        return leftDepth + 1;

    return rightDepth + 1;
}

/**
 * 按值查找
 */
int findByValue(BinTree tree, char x)
{
    if (tree == NULL)
        return 0;

    if (tree->data == x)
        return 1;

    int found = findByValue(tree->lchild, x);
    if (found)
        return 1;
    return findByValue(tree->rchild, x);
}

int main()
{
    // 最后一层上的所有层需要对齐补全: ABCDEFGHIJKLMNOPQRS
    char *treestr = "ABCDE@F"; // ABCD@FGHI@@@@@@@@R@
    // 完全二叉树层次(每层从左到右)输入字符串数组
    BinTree btree1 = createByCompleteTree();
    printf("\n前序遍历: ");
    s_preorder(btree1);
    printf("\n中序遍历: ");
    // inorder(btree1);
    // s_inorder(btree1);
    p_inorder(btree1);
    printf("\n层次遍历输出: ");
    transLevel(btree1);
    printf("\n");
    printf("求深度: %d\n", treeMaxDepth(btree1));
    printf("\n莫里斯前序遍历: ");
    morrisPreorder(btree1);
    printf("\n前序遍历: ");
    preorder(btree1);
    printf("\n中序遍历: ");
    inorder(btree1);
    printf("\n后序遍历: ");
    postorder(btree1);
    printf("\n输入查找的值: ");
    char findv = getchar();
    printf("查找结果: %s\n", findByValue(btree1, findv) ? "YES" : "NO");
    exit(0);
    // 广义表形式输入字符
    char *fixchararray = "(A,(B(,D(E,F)),C)";
    char *generalizestr = getCharList();
    printf("-------start create bintree: charlen=%lu>>>\n", strlen(generalizestr));
    // printchar(generalizestr);
    BinTree btree = createByGeneralize(generalizestr);
    printf("\n中序遍历:: ");
    inorder(btree);
    printf("\n");
    return 0;
}